public class MyDoubleLinkList <E> implements MyList<E>{
    /**
     * 定义双向链表的节点对象
     * @param element
     */

    class Node <E>{
        E item;
        Node<E> prev; //记录前一个节点对象
        Node<E> next; //记录下一个节点对象

        Node(Node<E> prev,E item, Node<E> next){
                 this.prev=prev;
                 this.item=item;
                 this.next=next;
        }
    }

private Node head;  //头节点
private Node tail;   //尾结点
private int size;    //元素个数


    @Override
    public void add(E element) {
   this.linkLast(element);
    }
//将节点添加到链表尾部
    private void linkLast(E element){
      //获取尾结点
        Node t=this.tail;
        //创建节点对象
        Node<E> node=new Node<>(t,element,null);
        //将新节点定义为尾结点
        this.tail=node;
        if(t==null){
            this.head=node;
        }else{
                t.next=node;
        }
        this.size++;

    }


    /**
     * 根据指定位置获取元素
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        //对index做合法性校验
        this.checkIndex(index);
        //根据位置查找节点对象
Node<E> node=this.getNode(index);
       return  node.item;
    }

    private  void checkIndex(int index){
        if((index>=0)&&(index<this.size)){
            throw new IndexOutOfBoundsException("index:"+index+"Size"+size);
        }
    }

    private  Node getNode(int index){
        //判断当前位置距离头或者尾哪个节点更近
        if(index<(this.size<<1) ){
            Node node=this.head;
            for(int i=0;i<index;i++){
                node=node.next;
            }
            return node;
        }else{
            Node node=this.tail;
            for(int i=this.size-1; i>index;i--){
                node=node.prev;
            }
            return node;
        }
    }
    /**
     * 返回对元素的个数
     * @return
     */
    @Override
    public int size() {
        return size;
    }


    /**
     * 根据指定位置删除元素
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        this.checkIndex(index);
        Node<E> node=this.getNode(index);
        E item=node.item;
        //判断当前节点是否为头结点
        if(node.prev==null){
            this.head=node.next;
        }else{
            node.prev.next=node.next;
        }
        if(node.next==null){
            this.tail=node.prev;

        }else{
            node.next.prev=node.prev;
        }

        //当前节点断掉与直接前驱节点的链接
        node.prev=null;
        //当前节点断掉与它后继节点的连接
        node.next=null;
        node.item=null;
        this.size--;
        return null;
    }

    public static void main(String[] args) {
        MyList<String> myList=new MyDoubleLinkList<>();
        myList.add("a");
        myList.add("b");
        myList.add("c");
        myList.add("d");
        System.out.println(myList.size());

        for (int i = 0; i < myList.size() ; i++) {
            System.out.println(myList.get(i));
        }
    }
}
